package com.yanceysong.codetop.s51_s60;


public class S55_Hard_76_最小覆盖子串 {
    /**
     * .题目：76. 最小覆盖子串 (Minimum Window Substring)
     * .<p>
     * .链接：<a href="https://leetcode.cn/problems/minimum-window-substring/">https://leetcode.cn/problems/minimum-window-substring/</a>
     * .<p>
     * .给你两个字符串 source (记为 s) 与 target (记为 t)，请你在 source 中找到一个最短的子串，
     * .这个子串包含 target 中所有字符（包括重复次数）。若不存在这样的子串，返回空串 ""。
     * .若存在，题目保证答案唯一。
     * .<p>
     * .示例1：
     * .输入：s = "ADOBECODEBANC", t = "ABC"
     * .输出："BANC"
     * .解释：最短的包含 'A','B','C' 的子串是 "BANC"。
     * .<p>
     * .示例2：
     * .输入：s = "a", t = "a"
     * .输出："a"
     * .<p>
     * .示例3：
     * .输入：s = "a", t = "aa"
     * .输出：""  (目标需要两个 'a'，源只有一个，无法满足)
     * .<p>
     * .核心标签：滑动窗口 / 双指针 / 字符统计 / 字符串 / 优化收缩
     * .<p>
     * .=====================
     * .一、问题本质
     * .=====================
     * .在一个字符串中，寻找「满足包含条件」且长度最小的区间。这是典型的「最短满足条件子串」问题，
     * .使用滑动窗口（双指针）框架：
     * .1. 右指针向右扩张，使窗口“足够好”（包含所有目标字符）
     * .2. 左指针向右收缩，剔除冗余字符，使窗口“尽可能小”且仍满足条件
     * .<p>
     * .=====================
     * .二、算法思路（本实现的特殊写法）
     * .=====================
     * .1. 使用 int[128] 数组 freqDelta 记录 target 的需求（只考虑 ASCII）
     * .   初始化时：对每个目标字符 c 执行 freqDelta[c]-- → 需求为负数，表示还欠多少个该字符
     * .2. 移动右指针 right：
     * .   - 读取字符 ch = source.charAt(right)
     * .   - 如果 freqDelta[ch] < 0，说明该字符仍是“欠缺”，将 matchedChars++
     * .   - 然后 freqDelta[ch]++（把该字符放入窗口，减少欠缺）
     * .3. 当 matchedChars == target.length()，说明窗口已经包含所有 target 的字符（含重复次数）
     * .   执行窗口左边界 left 的收缩：
     * .   - 当 freqDelta[source.charAt(left)] > 0 时，说明该字符在窗口中是“冗余”（出现次数超过需求），可以移除 → freqDelta[leftChar]--，left++
     * .4. 每次达到有效窗口后，尝试更新记录的最优答案（bestLen + bestStart）。
     * .5. 遍历结束，若 bestStart 未被更新（仍为-1），返回空串；否则返回最优子串。
     * .<p>
     * .=====================
     * .三、ASCII 过程示意（示例：s = ADOBECODEBANC, t = ABC）
     * .=====================
     * .初始：freqDelta['A']=-1, 'B'=-1, 'C'=-1，其余为0
     * .right 扩张：
     * . A D O B E C O D E B A N C
     * . ^                         （right=0，看到A，freqDelta[A] < 0 → matchedChars=1，再 freqDelta[A]++ -> 0）
     * . ...... 继续扩张直到首次 matchedChars == 3（包含 A,B,C）
     * .窗口为：ADOBEC (left=0,right=5) → 收缩左侧：
     * . 移除 A 会导致需求重新欠缺（freqDelta[A]==0，不能移除） → 停止收缩 → 当前候选长度6
     * .继续扩张到 BANC：
     * . ..................B A N C
     * .                    ^   ^ (left 向右收缩直到最短满足，得到 BANC 长度4，更新答案)
     * .<p>
     * .=====================
     * .四、为什么这种负数初始化方式有效？
     * .=====================
     * .1. 初始为负表示“欠缺”
     * .2. 每加入一个字符就 ++，直到 >=0 表示该字符需求已经满足或超额
     * .3. 在加入字符前先判断是否仍欠缺（freqDelta[ch] < 0）来统计 matchedChars
     * .4. matchedChars 达到 target 总长度（非去重）即可说明所有需求填满
     * .5. 收缩时只移除“超额字符”（freqDelta[leftChar] > 0），避免破坏需求满足状态
     * .<p>
     * .=====================
     * .五、复杂度分析
     * .=====================
     * .时间复杂度：O(n)，左右指针各最多移动 n 次
     * .空间复杂度：O(1)，使用固定大小的 128 数组（若字符集扩大到 Unicode，可改用 HashMap）
     * .<p>
     * .=====================
     * .六、常见坑点与关键洞察
     * .=====================
     * .1. matchedChars 统计的是 target 的总字符数，而不是“满足的字符种类数”
     * .2. 只有在 freqDelta[ch] < 0 时才能 matchedChars++，确保重复字符按需统计
     * .3. 收缩条件是 freqDelta[leftChar] > 0（即窗口内多了这个字符），不能错误写成 >= 0
     * .4. 若 target 长度大于 source，直接返回 ""，避免无谓计算
     * .5. 不需要额外记录窗口内每个字符的出现次数，再比较；负数初始化 + 正数回升即实现“欠缺 -> 满足 -> 冗余”三态判断
     * .<p>
     * .=====================
     * .七、对比常规写法（使用 needMap + haveCount）
     * .=====================
     * .本实现利用数组负数初始化技巧，减少了多余分支与额外 Map 判断，提高执行效率与可读性。
     */
    public String minWindow(String source, String target) {
        // 边界与快速失败检查：任一为空 或 target 比 source 长直接失败
        if (source == null || target == null || source.isEmpty() || target.isEmpty() || target.length() > source.length()) {
            return "";
        }

        int sourceLength = source.length();
        int targetLength = target.length();

        // needSurplusBalance：下标为字符的 ASCII 值；负数=还欠缺；0=刚好满足；正数=窗口多出的冗余数量
        int[] needSurplusBalance = new int[128];
        for (char c : target.toCharArray()) {
            needSurplusBalance[c]--; // 初始全部置为负，表示还需要这些字符
        }

        // 窗口相关变量
        int windowLeft = 0;                 // 当前有效窗口左边界
        int fulfilledTotalCount = 0;        // 已经满足的目标字符总数量（包含重复）
        int answerStart = -1;               // 最优解的起始位置
        int answerLength = sourceLength + 1; // 最优解长度（初始化为不可能的最大值）

        // 扩张窗口：windowRight 作为右指针遍历 source
        for (int windowRight = 0; windowRight < sourceLength; windowRight++) {
            char enteringChar = source.charAt(windowRight);
            // 进入前若 needSurplusBalance[enteringChar] < 0 表示“仍欠缺” → 此字符对满足目标有贡献
            if (needSurplusBalance[enteringChar] < 0) {
                fulfilledTotalCount++;
            }
            // 将该字符移入窗口：欠缺回升 或 变成冗余
            needSurplusBalance[enteringChar]++;

            // 当已经满足全部目标字符后（按总数量统计）尝试收缩左边界
            if (fulfilledTotalCount == targetLength) {
                // 移除冗余字符：只要最左侧字符的计数为正，说明它在窗口中是“多余”的，可以削减
                while (windowLeft < windowRight && needSurplusBalance[source.charAt(windowLeft)] > 0) {
                    needSurplusBalance[source.charAt(windowLeft)]--; // 移除一个冗余的出现次数
                    windowLeft++; // 收缩左边界
                }
                // 现在窗口 [windowLeft, windowRight] 是当前满足条件的最紧凑表示，尝试更新答案
                int currentWindowLen = windowRight - windowLeft + 1;
                if (currentWindowLen < answerLength) {
                    answerLength = currentWindowLen;
                    answerStart = windowLeft;
                }
            }
        }
        // 未找到任何满足条件的窗口
        return answerStart == -1 ? "" : source.substring(answerStart, answerStart + answerLength);
    }

    // -------------------------- 测试代码入口 -------------------------- //
    public static void main(String[] args) {
        S55_Hard_76_最小覆盖子串 solution = new S55_Hard_76_最小覆盖子串();
        System.out.println("=== 最小覆盖子串算法测试开始 ===\n");

        // 1. 基础示例：官方案例
        testCase(solution, "ADOBECODEBANC", "ABC", "BANC", "官方示例1");

        // 2. 单字符匹配
        testCase(solution, "a", "a", "a", "单字符匹配");

        // 3. 无法满足（目标长度大于源或源缺字符）
        testCase(solution, "a", "aa", "", "目标无法满足 (重复字符需求)");

        // 4. 含重复字符需求的场景
        testCase(solution, "AAABBC", "AABC", "AABBC", "重复字符需求场景");

        // 5. 最优窗口在后半部分
        testCase(solution, "XYZABBCZAB", "ABZ", "ZAB", "最优窗口出现在后半部分");

        // 6. 有多个候选窗口，取最短
        testCase(solution, "ABAACBAB", "ABC", "ACB", "多个候选窗口取最短");

        // 7. 冗余字符较多，需要强力收缩（最短窗口存在于中间）
        testCase(solution, "AAABAACBBBBC", "ABC", "ACB", "冗余字符强力收缩");

        // 8. 冗余+重复需求综合测试（需要 2 个 A + 1 个 B + 1 个 C），最短窗口应为 BAAC
        testCase(solution, "AAABAACBBBBC", "AABC", "BAAC", "冗余与重复需求综合 (最短窗口 BAAC)");

        // 9. 大量重复字符 + 稀疏目标
        testCase(solution, "aaaaaaaaabbbbbccccccddddd", "abcd", "abbbbbccccccd", "大量重复字符场景");

        // 10. 目标字符不存在于源
        testCase(solution, "ABCDEFG", "XYZ", "", "目标字符均不存在");

        // 11. 边界：空 target 或空 source
        testCase(solution, "", "ABC", "", "空源字符串");
        testCase(solution, "ABC", "", "", "空目标字符串");

        // 12. source 与 target 完全相同
        testCase(solution, "ABC", "ABC", "ABC", "源与目标完全一致");

        // 13. 最短窗口在开头
        testCase(solution, "ABCXXXXXX", "ABC", "ABC", "最短窗口在开头");

        // 14. 最短窗口在末尾
        testCase(solution, "XXXXXXABC", "ABC", "ABC", "最短窗口在末尾");

        // 15. 大数据规模性能冒烟测试
        String largeSource = "ADOBECODEBANC".repeat(300); // 适当缩减重复次数避免过长输出
        testCase(solution, largeSource, "ABC", "BANC", "大数据规模性能冒烟测试");

        System.out.println("\n=== 全部测试结束 ===");
    }

    /**
     * .单个测试用例执行与结果打印
     */
    private static void testCase(S55_Hard_76_最小覆盖子串 solution, String source, String target, String expected, String title) {
        String actual = solution.minWindow(source, target);
        boolean pass = actual.equals(expected);
        System.out.println("[" + title + "] source=" + source + ", target=" + target);
        System.out.println("  -> result=" + actual + ", expected=" + expected + ", pass=" + pass);
        assert pass : "测试失败: " + title + " (实际=" + actual + ", 期望=" + expected + ")";
    }
}
